// https://leetcode.cn/problems/evaluate-division/description/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 构建带权有向图表示变量间的除法关系
// 2. 使用广度优先搜索计算查询变量间的路径乘积
// 3. 预处理建立双向边，包含正反权重关系
// 4. 处理边界情况：变量不存在或起终点相同
// 5. 时间复杂度：O((E+Q)×V)，空间复杂度：O(E)

// 本题主函数由AI生成

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>

class Solution 
{
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) 
    {
        unordered_map<string, unordered_map<string, double>> graph;

        int equationNums = equations.size();
        for (int i = 0 ; i < equationNums ; i++)
        {
            const string& a = equations[i][0];
            const string& b = equations[i][1];
            double val = values[i];
            graph[a][b] = val;
            graph[b][a] = 1.0 / val;
        }

        vector<double> ret;
        ret.reserve(queries.size());
        int querieNums = queries.size();
        for (int i = 0 ; i < querieNums ; i++)
        {
            const string& start = queries[i][0];
            const string& end = queries[i][1];

            if (!graph.count(start) || !graph.count(end))
            {
                ret.push_back(-1.0);
                continue;
            }
            if (start == end)
            {
                ret.push_back(1.0);
                continue;
            }

            bool found = false;
            unordered_set<string> visited;
            queue<pair<string, double>> q;

            q.push({start, 1.0});
            visited.insert(start);

            while (!q.empty() && !found)
            {
                auto [curNode, curSum] = q.front();
                q.pop();

                for (auto& [nextNode, nextNum] : graph[curNode])
                {
                    if (nextNode == end)
                    {
                        found = true;
                        ret.push_back(curSum * nextNum);
                        break;
                    }

                    if (visited.insert(nextNode).second)
                    {
                        q.push({nextNode, curSum * nextNum});
                    }
                }
            }

            if (!found)
            {
                ret.push_back(-1.0);
            }
        }

        return ret;
    }
};

int main() 
{
    Solution solution;
    
    // 测试用例1
    vector<vector<string>> equations1 = {{"a","b"},{"b","c"}};
    vector<double> values1 = {2.0, 3.0};
    vector<vector<string>> queries1 = {{"a","c"},{"b","a"},{"a","e"},{"a","a"},{"x","x"}};
    
    vector<double> result1 = solution.calcEquation(equations1, values1, queries1);
    cout << "测试1结果: ";
    for (double val : result1) 
    {
        cout << val << " ";
    }
    cout << endl;  // 预期: 6 0.5 -1 1 -1
    
    // 测试用例2
    vector<vector<string>> equations2 = {{"a","b"}};
    vector<double> values2 = {0.5};
    vector<vector<string>> queries2 = {{"a","b"},{"b","a"},{"a","c"},{"x","y"}};
    
    vector<double> result2 = solution.calcEquation(equations2, values2, queries2);
    cout << "测试2结果: ";
    for (double val : result2) 
    {
        cout << val << " ";
    }
    cout << endl;  // 预期: 0.5 2 -1 -1
    
    return 0;
}